7/11
team virtual participation
实现一场训练 $0$ 罚时
训练四小时自闭两个小时二十分钟….
题目链接
A
签到
B
题意
二维平面内，给出n个点和m个平行坐标轴的矩形，问每个点被多少个矩形所包含(边界不算)。
$(n,m\le 10^5)$
题解
树状数组是单点更新区间查询 ! ! !
- 扫描线，离散化y坐标，对x坐标排序。
- 然后依次从小到大处理x，每一个x对应的y在线段树/树状数组更新即可。
C
模拟即可
D
题意
题解
E
题解
给两个凸多边形，问一个是否能包住另一个
题意
- 凸包模板题
- 两个点集的凸包如果是一个多边形的点即可。
- 注意对于在凸包上共线的点也要算入凸包的集合中。
F
- 因为是二叉树，暴力记录每个节点所在子树每层的和即可。
G
- 定义：$dp[i][j]$表示长度为 $i$ 以 $j$ 结束的最小花费。
- 转移：暴力转移即可。
- 时间复杂度 $O(k·26^2)$
H
题意
题解
I
题意
题解
J
签到